package sorting.programs.proper;

import java.util.ArrayList;
import java.util.List;

import sorting.programs.Sorting;

/*************************************************************************
 *  Compilation:  javac Merge.java
 *  Execution:    java Merge < input.txt
 *  Dependencies: StdOut.java StdIn.java
 *  Data files:   http://algs4.cs.princeton.edu/22mergesort/tiny.txt
 *                http://algs4.cs.princeton.edu/22mergesort/words3.txt
 *   
 *  Sorts a sequence of strings from standard input using mergesort.
 *   
 *  % more tiny.txt
 *  S O R T E X A M P L E
 *
 *  % java Merge < tiny.txt
 *  A E E L M O P R S T X                 [ one string per line ]
 *    
 *  % more words3.txt
 *  bed bug dad yes zoo ... all bad yet
 *  
 *  % java Merge < words3.txt
 *  all bad bed bug dad ... yes yet zoo    [ one string per line ]
 *  
 *************************************************************************/

public class SortingMerge implements Sorting {

    // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
    public static <T> void merge(Comparable<T>[] a, Comparable<T>[] aux, int lo, int mid, int hi) {
        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              a[k] = aux[j++];
            else if (j > hi)               a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else                           a[k] = aux[i++];
        }

    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static <T>void sort(Comparable<T>[] a, Comparable<T>[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public static <T> void sort(Comparable<T>[] a) {
        @SuppressWarnings("unchecked")
		Comparable<T>[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
    }
    
    public ArrayList<Integer> sort(List<Integer> a) {
    	Comparable<Integer>[] array = a.toArray(new Integer[0]);
        sort(array);
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (Comparable<Integer> comp : array)
        	result.add((Integer) comp);
        return result;
    }


   /***********************************************************************
    *  Helper sorting functions
    ***********************************************************************/
    
    // is v < w ?
    @SuppressWarnings("unchecked")
	private static <T> boolean less(Comparable<T> v, Comparable<T> w) {
        return (v.compareTo((T) w) < 0);
    }
}
